//二分 查找一个数的时候 while(l<=r)
//查找范围的边界点时 while(l<r)

//x的平方根
class Solution {
public:
    int mySqrt(int x) 
    {
        if(x==0) return 0;
        //因为只取整数部分
        //所以 mid*mid > x 则mid一定不是答案
        int l=1,r=x;
        while(l<r)
        {
            int mid=l+(r-l+1)/2;
            if(mid > x/mid) r=mid-1;
            else l=mid;
        }
        return l;
    }
};
//在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int>res;
        if(nums.size()==0) return {-1,-1};
        //求左端点
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(nums[mid]<target) l=mid+1;
            else r=mid;
        }
        if(nums[r]!=target) return {-1,-1};
        res.push_back(l);
        l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=(l+r+1)/2;
            if(nums[mid] > target) r=mid-1;
            else l=mid;
        }
        res.push_back(l);
        return res;
    }
};